/***************************************************************************************
* Copyright (c) 2014-2022 Zihao Yu, Nanjing University
*
* NEMU is licensed under Mulan PSL v2.
* You can use this software according to the terms and conditions of the Mulan PSL v2.
* You may obtain a copy of Mulan PSL v2 at:
*          http://license.coscl.org.cn/MulanPSL2
*
* THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND,
* EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,
* MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
*
* See the Mulan PSL v2 for more details.
***************************************************************************************/

#include <isa.h>
#include <memory/vaddr.h>
/* We use the POSIX regex functions to process regular expressions.
 * Type 'man regex' for more information about POSIX regex functions.
 */
#include <regex.h>

enum
{
  TK_NOTYPE = 256,
  TK_EQ,
  TK_NUM,
  TK_REG,
  TK_EQUAL,
  TK_AND,
  TK_OR,
  TK_DEREF,
  TK_NEG
  /* TODO: Add more token types */

};

static struct rule {
  const char *regex;
  int token_type;
} rules[] = {

  /* TODO: Add more rules.
   * Pay attention to the precedence level of different rules.
   */

  {" +", TK_NOTYPE},    // spaces
  {"\t+", TK_NOTYPE}, 
  {"\n+", TK_NOTYPE}, 
  {"\\+", '+'},         // plus
  {"\\-", '-'},         // minus
  {"\\*", '*'},         // multiple
  {"\\/", '/'},         // divide
  {"\\(", '('},         // bracket 
  {"\\)", ')'},         // inverse bracket 
  {"==", TK_EQUAL},
  {"&&", TK_AND},
  {"\\|\\|", TK_OR},
  {"\\$[A-Za-z0-9]+", TK_REG},
  {"0x[A-Fa-f0-9]+", TK_NUM},  // hex
  {"[0-9]+", TK_NUM},    // integer
  {"==", TK_EQ}        // equal
};

#define NR_REGEX ARRLEN(rules)

static regex_t re[NR_REGEX] = {};

/* Rules are used for many times.
 * Therefore we compile them only once before any usage.
 */
void init_regex() {
  int i;
  char error_msg[128];
  int ret;

  for (i = 0; i < NR_REGEX; i ++) {
    ret = regcomp(&re[i], rules[i].regex, REG_EXTENDED);
    if (ret != 0) {
      regerror(ret, &re[i], error_msg, 128);
      panic("regex compilation failed: %s\n%s", error_msg, rules[i].regex);
    }
  }
}

typedef struct token {
  int type;
  char str[32];
} Token;

static Token tokens[32] __attribute__((used)) = {};
static int nr_token __attribute__((used))  = 0;

static bool make_token(char *e) {
  int position = 0;
  int i;
  regmatch_t pmatch;

  nr_token = 0;

  while (e[position] != '\0') {
    /* Try all rules one by one. */
    for (i = 0; i < NR_REGEX; i ++) {
      if (regexec(&re[i], e + position, 1, &pmatch, 0) == 0 && pmatch.rm_so == 0) {
        int substr_len = pmatch.rm_eo;
#ifdef CONFIG_LOG_TOKEN
        char *substr_start = e + position;
        Log("match rules[%d] = \"%s\" at position %d with len %d: %.*s",
            i, rules[i].regex, position, substr_len, substr_len, substr_start);
#endif
        /* TODO: Now a new token is recognized with rules[i]. Add codes
         * to record the token in the array `tokens'. For certain types
         * of tokens, some extra actions should be performed.
         */

        switch (rules[i].token_type) {
          case TK_NOTYPE:
            break;
          default: 
            assert(substr_len < 31);
            strncpy(tokens[nr_token].str, e + position, substr_len);
            tokens[nr_token].str[substr_len] = '\0';
            tokens[nr_token].type = rules[i].token_type;
            nr_token++;
            break;
        }

        position += substr_len;
        break;
      }
    }

    if (i == NR_REGEX) {
      printf("no match at position %d\n%s\n%*.s^\n", position, e, position, "");
      return false;
    }
  }

  return true;
}

bool check_parentheses(int p, int q){
  return tokens[p].type == '(' && tokens[q].type == ')';
}

typedef struct token_prio
{
  int token_type;
  int prio;
} token_prio;

static token_prio prio_table[] = {
  {TK_OR, 11},
  {TK_AND, 10},
  {TK_EQUAL, 9},
  {'+', 7},
  {'-', 7},
  {'*', 6},
  {'/', 6},
  {TK_DEREF, 5},
  {TK_NEG, 5},
};
#define NR_TK_PRIO ARRLEN(prio_table)

static int get_token_prio(int token_type) {
  for (int i = 0; i < NR_TK_PRIO; i++)
    if (prio_table[i].token_type == token_type) return prio_table[i].prio;
  return -1;
}

static int find_op(int p, int q) {
  int op = -1;
  int prio = 0, temp_prio;
  bool in_parentheses = false;
  for (int c = p; c <= q; c++) {
    switch (tokens[c].type)
    {
    case '(':
      in_parentheses = true;
      break;
    case ')':
      in_parentheses = false;
      break;
    default:
      temp_prio = get_token_prio(tokens[c].type);
      if (!in_parentheses && prio < temp_prio) {
        prio = temp_prio;
        op = c;
      }
      break;
    }
  }
  return op;
}

word_t eval(int p, int q, bool *success) {
  if (p > q) {
    /* Bad expression */
    *success = false;
    return 0;    
  }
  else if (p == q) {
    /* Single token.
     * For now this token should be a number.
     * Return the value of the number.
     */
    switch (tokens[p].type)
    {
    case TK_NUM:
      /* code */
      return strtol(tokens[p].str, NULL, 0);
    case TK_REG:
      return isa_reg_str2val(tokens[p].str + 1, success);;
    default:
      *success = false;
      return 0;
    }
  }
  else if (check_parentheses(p, q) == true) {
    /* The expression is surrounded by a matched pair of parentheses.
     * If that is the case, just throw away the parentheses.
     */
    return eval(p + 1, q - 1, success);
  }
  else {
    int op = find_op(p, q);
    if(op < p) {
      *success = false;
      return 0;
    }
    if(op == p) {

      uint64_t val0 = eval(p + 1, q, success);
      switch (tokens[op].type)
      {
      case TK_NEG: return val0 * -1;
      case TK_DEREF: return *success ? vaddr_read(val0, 4) : 0;
      default: assert(0);
      }
    }
    else {

      uint64_t val1 = eval(p, op - 1, success);
      uint64_t val2 = eval(op + 1, q, success);
     
      switch (tokens[op].type) 
      {
      case '+': return val1 + val2;
      case '-': return val1 - val2;
      case '*': return val1 * val2;
      case '/': 
        if(val2 == 0) {
          *success = false;
          printf("expression error: divide zero\n");
          return 0;
        }
        return val1 / val2;
      case TK_AND: return val1 && val2;
      case TK_OR: return val1 || val2;
      case TK_EQUAL: return val1 == val2;
      default: assert(0);
      }
    }
  }
}

static bool is_operator(int i) {
  switch (i) { case TK_NUM: case TK_REG: return false; default: return true; }
}


word_t expr(char *e, bool *success) {
  if (!make_token(e)) {
    *success = false;
    return 0;
  }
  for (int i = 0; i < nr_token; i++) {
    if (tokens[i].type == '-' && (i == 0 || is_operator(tokens[i - 1].type))) {
      tokens[i].type = TK_NEG;
    }
    else if (tokens[i].type == '*' && (i == 0 || is_operator(tokens[i - 1].type))) {
      tokens[i].type = TK_DEREF;
    }
  }
  /* TODO: Insert codes to evaluate the expression. */
  return eval(0, nr_token - 1, success);
}
